1. Field of the Invention
This invention relates to the field of digital communication systems such as those that might be used for satellite transmission channels and cable channels, and in particular to error burst detectors which are used for improved decoding of error correction coded signals.
2. Description of the Relevant Art
The history of error correction coding begins with a discovery that any communications channel has a calculable capacity such that information transmission at a rate which does not exceed the capacity can be achieved with as small an error rate as desired. This information transmission is accomplished via the use of error correction coding. The discovery was based on ensemble averages, and consequently did not provide a useful code construction technique. An extensive amount of effort was expended in developing explicit code constructions which would provide asymptotically vanishing error rates, without success. The class of Hamming codes was then introduced, but these codes were only capable of correcting single errors. Other block codes were later developed, but they were accompanied by no general construction theory. In the late 1950's, a probabilistic approach to the decoding problem led to the development of tree codes, which have been primarily represented by convolutional codes. Then around 1960, Reed-Solomon codes and the more general Bose-Chadhuri-Hocquenghem codes provided a large class of multiple error correcting codes, which comprise one of the most important classes of block codes today. However, the performance of these codes suffers when extended to large block lengths. In the late 1960's and early 1970's the Viterbi decoder was introduced as a replacement for the sequential decoding of tree codes, thereby strengthening the feasibility of convolutional coding. Finally, in the 1970's the Justesen and Goppa code families were introduced which provided good codes with long block lengths, albeit with significantly more complex decoding algorithms.
Error control codes function by accepting input data symbols and processing them in such a way as to add some redundancy to the symbol sequence. All error control codes can be formulated so that this coding process takes the form of adding check symbols to the data symbol sequence. With this formulation, the encoder accepts an input word of k data symbols at each time step and produces a code word with n symbols, k of which are the input data symbols, and n-k of which are the check symbols. An example of such a code word 10 having k data symbols 12 and n-k check symbols 14 is shown in FIG. 1. The redundancy added by the check symbols serves to increase the distance between valid code symbol sequences. A common measure of the distance between two code words is the number of symbols in which they differ, defined herein as the Hamming distance. Shown in FIG. 2 are two code words 16 and 18 which are selected from the set of valid code words that make up an example block code. A comparison of two code words 16 and 18, shown in FIG. 2 reveals three symbol positions which differ: D.sub.3, D.sub.5, and D.sub.7. Thus the Hamming distance between code words 16 and 18 is three. The minimum Hamming distance between any two sequences of code words is called the minimum Hamming distance of the code, and is often denoted d.sup.H.sub.min. For a block code, each code word in the sequence is unrelated to other code words, so this distance corresponds to the minimum Hamming distance between any two code words. In FIG. 2, the code words 16 and 18 are the nearest valid code words, so for this code d.sup.H.sub.min =3.
When code words are transmitted across a noisy channel, they are often subject to corruption. This corruption typically takes the form of symbol errors in the code word. Usually the locations of these errors are unknown prior to decoding, but in some cases it is possible to determine the locations of these errors prior to decoding. When this occurs, it is advantageous to mark their locations in some manner so that these symbols are disregarded in the decoding process. When this is done, these errors which are characterized by an unknown error value but a known error location can be referred to as erasures. The circumstances under which the code word will be correctly decoded are provided by the following equation : EQU n.sub.E +2n.sub.c .ltoreq.d.sub.min.sup.H -1,
where n.sub.E is the number of erasures and n.sub.e is the number of errors.
To illustrate the above equation, assume that code word 18 is transmitted and received as a corrupted code word 20 with two symbol errors. Consider the well known decoding algorithm wherein the received code word is compared to all valid code words, and the valid code word that is most like the received code word is chosen as the correct code word. Decoding is then accomplished by simply removing the check symbols from the chosen code word. In FIG. 2 code word 20 represents a received code word that contains two symbol errors. According to the equation, code word 20 may be incorrectly decoded, and indeed it differs by only one symbol from code word 16. According to the stated decoding algorithm, incorrect code word 16 is chosen, resulting in a decoding error. However, when the knowledge of the error locations is applied as shown by code word 22, then these symbols are ignored in the comparison process and code word 22 matches the correct code word 18. Consequently code word 22 with erasures is correctly decoded. In general, the number of erasures that a code can tolerate without making decision errors is twice the number of unerased errors that it can tolerate. Further details on the design and function of error correction codes may be found in Bernard Sklar, Digital Communications: Fundamentals and Applications, Prentice Hall, Englewood Cliffs N.J., pp. 263-365, 1988, incorporated herein by reference.
While this relation between error and erasure tolerance is well known, a practical mechanism for detecting error locations with high probability before decoding is not. The above equation shows that erasures and errors both impair the ability to decode correctly, and the only advantage gained by using erasures is the provision of additional side information to the decoder. When erasures are misapplied, that is, when the location of errors is misidentified, then decoding performance worsens.
The art of code design revolves around optimizing the tradeoff between code rate and Hamming distance gain for a given code complexity. Reed-Solomon codes are extremely popular because this family of codes is based on a construction that allows for custom tailoring of the information rate and Hamming distance properties of the code. Furthermore, efficient decoders are easy to design for these codes. However at large block lengths, the performance of Reed-Solomon codes suffers a loss of efficiency. A technique for extending the effective block length of these codes is to follow the Reed-Solomon encoder with an interleaver which acts to intersperse the symbols from one code word with the symbols from other code words. This is typically done by writing the code words into a memory matrix column-wise and reading the completed matrix row-wise. The interleaver can then be followed by a convolutional encoder which further adds redundancy to the symbol sequence. At the receiving end the process is reversed, first applying a convolutional decoder to the received sequence, next applying a de-interleaver, and finally performing the Reed-Solomon block decode. Each of the additional steps adds only a moderate amount of complexity to the system while significantly boosting its performance.
This arrangement is typically used in environments where code symbol errors caused by the channel can occur in bursts. Burst errors are not random isolated errors, but rather burst errors are defined as errors which occur in localized groups. Apart from the random uncorrelated noise, other effects may corrupt the transmitted signal. These effects are more bursty in nature (examples: microwave radiation close to the receiving antenna, lightning, home appliance electrical noise, etc.). The de-interleaver acts to distribute errors within a group so that they are isolated and fewer occur within a given code word. This in turn enhances the probability that the number of errors will not exceed the correction capability of the Reed-Solomon code. Nevertheless, it is still necessary to use Reed-Solomon codes of moderate length and complexity to keep the error correction capability high enough to preserve their resistance to burst errors.
Since error correction coding necessitates the transmission of check symbols in addition to the data symbols, the bandwidth available to the data symbols can be decreased to make room for the check symbols, or additional bandwidth can be allocated for the check symbols. The first option results in a reduction of the rate at which data can be transmitted, and the second option results in an increase in overall channel bandwidth. Typically one of these options is required, but the tradeoff is increased manufacturing tolerances, increased margin for equipment degradation, a reduction of the required signal-to-noise ratio, and an overall reduced probability of error.
Hence, error correction coding produces desirable performance gains in digital communication systems. This gain can be enhanced by a method for error burst detection.